home *** CD-ROM | disk | FTP | other *** search
/ AOL File Library: 2,801 to 2,900 / aol-file-protocol-4400-2801-to-2900.zip / AOLDLs / C++ Files Library / CustomNew.cp / CustomNew.cp next >
Text File  |  2014-09-28  |  8KB  |  224 lines
  1. // CustomNew.p by Franìois Pottier (pottier@clipper.ens.fr)
  2. // December 1st, 1994
  3.  
  4. // --- WHAT IT IS - HOW TO USE IT ---------------------------------------------------------------------------------------
  5.  
  6. // This file redefines the standard new and delete operators.
  7.  
  8. // Advantages over MetroWerks's definition:
  9. // 1. Memory is taken from the application heap or the temporary heap (preferrably the first) for greater flexibility.
  10. // 2. Unused memory pools are released to the system.
  11. // 3. Less fragmentation, because the MetroWerks delete operator doesn't always join adjacent free blocks.
  12. // 4. If pool allocation fails, new doesn't revert to calling NewPtr for each block. It's a good thing, because otherwise the program
  13. //     would just slow down to a crawl (NewPtr is much slower than new) and die a horrible death, should the Toolbox run out of space.
  14.  
  15. // Finally, I keep a count of used blocks and free blocks, which can help assess the program's memory usage and fragmentation.
  16.  
  17. // How to use:
  18. // - Add CustomNew.cp to your project.
  19.  
  20. // --- LEGAL TERMS -----------------------------------------------------------------------------------------------------
  21.  
  22. // Although I wrote these routines entirely myself, they are loosely based on MetroWerks code.
  23. // As far as I am concerned, you can use them freely in any of your programs. My only request is that you notify me if you find
  24. // bugs or devise improvements. My email address is pottier@clipper.ens.fr
  25.  
  26. // Remember, this code has NOT been THOROUGHLY TESTED!
  27.  
  28. // --- OK FOLKS, LET'S HAVE THE CODE ------------------------------------------------------------------------------------
  29.  
  30. #include <stddef.h>
  31.  
  32. enum {
  33.     kPoolSize = 65536L,                                    // Memory is allocated in 64K chunks
  34.     kBigSize = 2048L                                    // Any allocations bigger than 2K go through the OS directly
  35. };
  36.  
  37. typedef struct FreeMemList {                            // Free blocks are linked together in a list
  38.     struct FreeMemList    *next;                            // Pointer to next free block
  39.     long                size;                            // Size of this block
  40. } FreeMemList;
  41.  
  42. typedef struct MemPool {                                // Memory is allocated from pools (locked handles)
  43.     struct MemPool        *next;                            // Pointer to next pool
  44.     FreeMemList            *freeHead;                        // Start of free blocks list
  45.     long                usedBlocks, freeBlocks;            // Statistics
  46.     Byte                data[];                            // Blocks
  47. } MemPool;
  48.  
  49. MemPool*                gPoolHead = NULL;                // List of pools
  50.  
  51. long BytesTakenFromTempZone (void);
  52.  
  53. static Handle MakeLockedHandle (long size)                // Create a locked handle from the application heap
  54. {                                                        // or the temporary zone
  55.     Handle            h;
  56.     OSErr            e;
  57.  
  58.     h = NewHandle(size);
  59.     if (h == NULL)  {
  60.         h = TempNewHandle(size, &e);
  61.         if ( h ) HLock(h);
  62.     }
  63.     else
  64.         HLockHi(h);
  65.     return h;
  66. }
  67.  
  68. static Boolean NewPool (void)                            // Add a new pool to the pool list
  69. {
  70.     Handle            h;
  71.     MemPool*            pool;
  72.     
  73.     h = MakeLockedHandle(kPoolSize);
  74.     if (h == NULL)
  75.         return false;
  76.     pool = (MemPool*) *h;
  77.     
  78.     pool->next = gPoolHead;
  79.     pool->freeHead = (FreeMemList*) pool->data;
  80.     pool->freeHead->next = NULL;
  81.     pool->freeHead->size = (Ptr) pool + kPoolSize - (Ptr) pool->data;
  82.     pool->usedBlocks = 0;
  83.     pool->freeBlocks = 1;
  84.     gPoolHead = pool;
  85.  
  86.     return true;
  87. }
  88.  
  89. static void* AllocFromPool (MemPool* pool, long size)
  90. {
  91.     FreeMemList        *block;                                // The block under consideration
  92.     FreeMemList*        *link;                                // The place which points to block in the free blocks list
  93.     Ptr                result;
  94.     
  95.     for (link = &pool->freeHead; (block = *link) != nil; link = &block->next)    // Walk the free blocks list
  96.         if (size <= block->size) {                                // If a free block is big enough
  97.             if (block->size >= size + sizeof(FreeMemList)) {        // If it's really big enough, we can split it
  98.                 block->size -= size;                            // The low part remains a free block
  99.                 result = (Ptr) block + block->size;                // The high part becomes allocated
  100.             }
  101.             else {                                        // If it's just big enough, we can't split it
  102.                 *link = block->next;                            // So we remove it from the free blocks list
  103.                 result = (Ptr) block;                            // And we mark it all as allocated
  104.                 pool->freeBlocks--;
  105.             }
  106.             pool->usedBlocks++;
  107.             * (long*) result = size;                            // The first four bytes contain the new block's size
  108.             return (result + 4);
  109.         }
  110.     
  111.     return NULL;
  112. }
  113.  
  114. // We assume the free blocks list to be always ordered from bottom to top, and it is because we insert new free blocks in the right
  115. // place. This allows us to easily join adjacent free blocks into a single one when deleting a block, thus reducing stupid fragmentation.
  116.  
  117. static void DeleteFromPool (MemPool* pool, Ptr pointer, long size)
  118. {
  119.     FreeMemList        *block, *previous, *next;
  120.     FreeMemList*        *link;
  121.     
  122.     previous = next = NULL;                                    // Look for any adjacent free blocks
  123.     for (link = &pool->freeHead; (block = *link) != nil; link = &block->next)    // Walk the free blocks list
  124.         if (pointer == (Ptr) block + block->size)                    // We have found a free block just before ours
  125.             previous = block;
  126.         else if (pointer + size == (Ptr) block) {                    // We have found a free block just after ours
  127.             next = block;
  128.             goto Coalesce;                                    // Stop searching now, there's nothing more up there and we will need the value of link
  129.         }
  130.         else if (pointer + size < (Ptr) block)                        // We have found no adjacent block
  131.             goto Coalesce;                                    // The current value of link tells us where to insert the new free block
  132.     
  133. Coalesce:
  134.     pool->usedBlocks--;
  135.     if (previous != NULL && next != NULL) {                        // We now have 3 free blocks, join them
  136.         previous->size += size + next->size;
  137.         previous->next = next->next;
  138.         pool->freeBlocks--;
  139.     }
  140.     else if (previous)                                        // Expand the free block below
  141.         previous->size += size;
  142.     else if (next) {                                            // Expand the free block above
  143.         ((FreeMemList*) pointer)->next = next->next;
  144.         ((FreeMemList*) pointer)->size = next->size + size;
  145.         *link = (FreeMemList*) pointer;
  146.     }
  147.     else {                                                // Add a free block to the list
  148.         ((FreeMemList*) pointer)->next = *link;
  149.         ((FreeMemList*) pointer)->size = size;
  150.         *link = (FreeMemList*) pointer;
  151.         pool->freeBlocks++;
  152.     }    
  153. }
  154.  
  155. void *operator new (size_t size)
  156. {
  157.     MemPool*            pool;
  158.     void*            result;
  159.  
  160.     size = (size & 0xFFFFFFFC) + 8;                            // Make sure size is a multiple of 4, and add 4 bytes to store the block size
  161.  
  162.     if (size >= kBigSize) {                                    // If the requested size is big
  163.         Handle h = MakeLockedHandle(size);                        // Use the Memory Manager directly
  164.         if (h == NULL)
  165.             return NULL;
  166.         * (long*) *h = -1L;                                    // This special value serves to recognize standalone blocks
  167.         return (*h + 4);
  168.     }
  169.     
  170.     pool = gPoolHead;                                        // Try to find a pool with enough room
  171.     while (pool) {
  172.         if ( (result = AllocFromPool(pool, size)) != nil )
  173.             return result;
  174.         pool = pool->next;
  175.     }
  176.     
  177.     if (NewPool())                                            // If no pool has enough space, create a new pool
  178.         return AllocFromPool(gPoolHead, size);
  179.     return NULL;                                            // If we can't create a new pool, fail - *don't* revert to NewPtr, it's too damn slow and would hopelessly fill up the heap
  180. }
  181.  
  182. void operator delete (void *pointer)
  183. {
  184.     long                size;
  185.     MemPool*            pool;
  186.     MemPool*            *link;
  187.  
  188.     if (pointer) {
  189.         pointer = (Ptr) pointer - 4;                            // Retrieve the block size, which is stored 4 bytes below
  190.         size = * (long*) pointer;
  191.  
  192.         if (size == -1L)                                        // If the size tag is -1, the block is a handle
  193.             DisposeHandle(RecoverHandle((Ptr) pointer));
  194.         else {
  195.             link = &gPoolHead;                                // Find which pools the block belongs to
  196.             while ((pool = *link) != nil && ((Ptr) pointer < (Ptr) pool || (Ptr) pointer > (Ptr) pool + kPoolSize))
  197.                 link = &pool->next;
  198.  
  199.             DeleteFromPool(pool, (Ptr) pointer, size);                // Delete the block from this pool
  200.             
  201.             if (pool->usedBlocks == 0) {                        // If this pool isn't used any more
  202.                 *link = pool->next;                            // Remove it from the pool queue
  203.                 DisposeHandle(RecoverHandle((Ptr) pool));        // And release it
  204.             }
  205.         }
  206.     }
  207. }
  208.  
  209. long BytesTakenFromTempZone (void)                            // For informational purposes, returns the number of
  210. {                                                        // bytes taken from the Multifinder zone. Note that this
  211.     MemPool*            pool;                                    // figure takes only pools into accounts, not stand-alone
  212.     Handle            h;                                    // blocks.
  213.     long                size;
  214.     
  215.     size = 0;
  216.     for (pool = gPoolHead; pool; pool = pool->next) {
  217.         h = RecoverHandle((Ptr) pool);
  218.         if (HandleZone(h) != ApplicZone())
  219.             size += GetHandleSize(h);
  220.     }
  221.     return size;
  222. }
  223.  
  224. // THAT'S ALL FOLKS. HOPE YOU ENJOYED THE SHOW -----------------------------------------------------------------------